package com.zj.leetcode.medium.greed;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: algorithm
 * @description: 插入区间
 * 57 insert-interval
 * @author: Zhang Bo
 * @create: 2022-03-24 10:53:48
 **/
public class InsertInterval {
    public static void main(String[] args) {
        int[] newInterval = new int[]{2, 3};
        Solution solution = new InsertInterval().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[][] insert(int[][] intervals, int[] newInterval) {
            if (intervals.length == 0) {
                return new int[][]{{newInterval[0], newInterval[1]}};
            }

            int left = newInterval[0];
            int right = newInterval[1];

            boolean flag = false;
            List<int[]> arr = new ArrayList<>();
            for (int i = 0; i < intervals.length; i++) {

                if (intervals[i][0] > right) {
                    if (!flag) {
                        flag = true;
                        arr.add(new int[]{left, right});
                    }
                    arr.add(intervals[i]);
                } else if(intervals[i][1] < left){
                    arr.add(intervals[i]);
                } else {
                    left = Math.min(left, intervals[i][0]);
                    right = Math.max(right, intervals[i][1]);
                }
            }

            if (!flag) {
                arr.add(new int[]{left, right});
            }
            return arr.toArray(new int[arr.size()][2]);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
